package com.future;

import java.util.Arrays;

/**
 * Description:1707. ��������Ԫ�ص�������ֵ ����ˢ���6��
 * ����һ���ɷǸ�������ɵ����� nums ������һ����ѯ���� queries ������ queries[i] = [xi, mi] ��
 * <p>
 * �� i ����ѯ�Ĵ��� xi ���κ� nums �����в����� mi ��Ԫ�ذ�λ���XOR���õ������ֵ�����仰˵������ max(nums[j] XOR xi) ��
 * �������� j ������ nums[j] <= mi ����� nums �е�����Ԫ�ض����� mi�����մ𰸾��� -1 ��
 * <p>
 * ����һ���������� answer ��Ϊ��ѯ�Ĵ𰸣����� answer.length == queries.length �� answer[i] �ǵ� i ����ѯ�Ĵ𰸡�
 * <p>
 * ʾ�� 1��
 * <p>
 * ���룺nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
 * �����[3,3,7]
 * ���ͣ�
 * 1) 0 �� 1 �ǽ��е����������� 1 ��������0 XOR 3 = 3 �� 1 XOR 3 = 2 �������еĸ���ֵ�� 3 ��
 * 2) 1 XOR 2 = 3.
 * 3) 5 XOR 2 = 7.
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/maximum-xor-with-an-element-from-array
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @author weiruibai.vendor
 * Date: 2022/4/20 09:30
 */
public class Solution_1707 {

    public static void main(String[] args) {

        int[] nums = {0, 1, 2, 3, 4};
        int[][] queries = {{3, 1}, {1, 3}, {5, 6}};
        nums = new int[]{5, 2, 4, 6, 6, 3};
        queries = new int[][]{{12, 4}, {8, 1}, {6, 3}};
        System.out.println(Arrays.toString(maximizeXor(nums, queries)));
        System.out.println(Arrays.toString(maximizeXor_v2(nums, queries)));
    }

    /**
     * ��Ч����
     *
     * @param nums
     * @param queries
     * @return
     */
    public static int[] maximizeXor_v2(int[] nums, int[][] queries) {
        if (nums == null || queries == null) {
            return nums;
        }
        NumTrie numTrie = new NumTrie();
        for (Integer num : nums) {
            numTrie.add(num);
        }
        int M = queries.length;
        int[] res = new int[M];
        for (int i = 0; i < M; i++) {
            res[i] = numTrie.getMaximizeXor(queries[i][0], queries[i][1]);
        }
        return res;
    }

    private static class NumTrie {
        // �ύ��ȥֵ������30������Ϊ�˲��ԣ���������Сһ�㷽��debug
        private static final int maxHeight = 30;
        public Node head;


        public NumTrie() {
            this.head = new Node();
        }

        /**
         * �����߶���
         *
         * @param num
         */
        public void add(int num) {
            Node cur = head;
            // ���µ�ǰ����ֵ
            cur.min = Math.min(cur.min, num);
            for (int move = maxHeight; move >= 0; move--) {
                int path = (num >> move) & 1;
                cur.nexts[path] = cur.nexts[path] == null ? new Node() : cur.nexts[path];
                cur = cur.nexts[path];
                cur.level = move;
                // ���µ�ǰ��Сֵ
                cur.min = Math.min(cur.min, num);
            }
        }

        public int getMaximizeXor(int target, int max) {
            if (head.min > max) {
                return -1;
            }
            int ans = 0;
            Node cur = head;
            for (int move = maxHeight; move >= 0; move--) {
                int path = (target >> move) & 1;
                int best = path ^ 1;
                int realPath = (cur.nexts[best] == null || cur.nexts[best].min > max) ? best ^ 1 : best;
                ans |= (path ^ realPath) << move;
                cur = cur.nexts[realPath];
            }
            return ans;
        }
    }

    private static class Node {
        public int min;// ��¼��ǰ��Сֵ
        public Node[] nexts;
        public int level;// ���˵�ǰ�߶�,��ҪΪ�˷���debug������ǰ�����ĸ����

        public Node() {
            this.min = Integer.MAX_VALUE;
            nexts = new Node[2];
        }
    }

    /**
     * ��������
     *
     * @param nums
     * @param queries
     * @return
     */
    public static int[] maximizeXor(int[] nums, int[][] queries) {
        if (nums == null || queries == null) {
            return nums;
        }
        int N = nums.length;
        int M = queries.length;
        int[] res = new int[M];
        Arrays.sort(nums);
        for (int i = 0; i < M; i++) {
            int ans = -1;
            int target = queries[i][0];
            int lessNum = queries[i][1];
            for (int j = 0; j < N && nums[j] <= lessNum; j++) {
                ans = Math.max(ans, target ^ nums[j]);
            }
            res[i] = ans;
        }
        return res;
    }
}
